602C - The Two Routes - CodeForces Solution

import collections
n,r=map(int,input().split())
train={i:[] for i in range(1,n+1)}
bus={i:[j for j in range(1,n+1) if j!=i] for i in range(1,n+1)}
for i in range(r):
    a,b=map(int,input().split())
    train[a].append(b)
    train[b].append(a)
    bus[a].remove(b)
    bus[b].remove(a)
def bfs(s,dic):
    q=collections.deque([[s,0]])
    vis=set([s])
    t=-1
    while q:
        a,b=q.popleft()
        if a==n:
            t=b
            break
        for i in dic[a]:
            if i not in vis:
              vis.add(i)
              q.append([i,b+1])
    return t

a=(bfs(1,train))
b=(bfs(1,bus))
if a<0 or b<0:
    print(-1)
else:
    print(max(a,b))